package 极客算法训练营.chapter04;

/**
 * MyCircularDeque(k)：构造函数,双端队列的大小为k。
 * insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
 * insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
 * deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
 * deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
 * getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
 * getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
 * isEmpty()：检查双端队列是否为空。
 * isFull()：检查双端队列是否满了。
 */
public class 设计循环双端队列 {
    public static void main(String[] args) {

    }

    class MyCircularDeque {

        class Node {
            private int val;
            private Node pre;
            private Node next;

            public Node(int val) {
                this.val = val;
            }
        }

        private Node head;
        private Node end;
        private Integer size;
        private Integer count;

        /**
         * Initialize your data structure here. Set the size of the deque to be k.
         */
        public MyCircularDeque(int k) {
            size = k;
        }

        /**
         * Adds an item at the front of Deque. Return true if the operation is successful.
         */
        public boolean insertFront(int value) {
            //先判断空间是否溢出
            if (count != null && count >= size) return false;
            //创建结点
            Node new_Node = new Node(value);
            //链表为空时
            if (head == null && end == null) {
                head = end = new_Node;
                count = 1;
                return true;
            }
            //链表不为空时
            new_Node.next = head;
            head.pre = new_Node;
            head = new_Node;
            count++;
            return true;
        }

        /**
         * Adds an item at the rear of Deque. Return true if the operation is successful.
         */
        public boolean insertLast(int value) {
            //先判断空间是否溢出
            if (count != null && count >= size) return false;
            Node new_Node = new Node(value);
            //链表为空时
            if (head == null && end == null) {
                head = end = new_Node;
                count = 1;
            } else {
                //链表不为空时
                end.next = new_Node;
                new_Node.pre = end;
                end = new_Node;
                count++;
            }
            return true;
        }

        /**
         * Deletes an item from the front of Deque. Return true if the operation is successful.
         */
        public boolean deleteFront() {
            //没有元素
            if (head == null) return false;
            //只剩一个元素
            if (head != null && head.next == null) {
                head = end = null;
            } else {
                //剩余元素大于1
                Node second = head.next;
                second.pre = null;
                head = second;
            }
            count --;
            return true;
        }

        /**
         * Deletes an item from the rear of Deque. Return true if the operation is successful.
         */
        public boolean deleteLast() {
            //没有元素
            if (end == null) return false;
            //只剩一个元素
            if (end != null && end.pre == null) {
                end = head = null;
            } else {
                //剩余元素大于1
                Node _second = end.pre;
                _second.next = null;
                end = _second;
            }
            count --;
            return true;
        }

        /**
         * Get the front item from the deque.
         */
        public int getFront() {
            if (head == null) return -1;
            return head.val;
        }

        /**
         * Get the last item from the deque.
         */
        public int getRear() {
            if (end == null) return -1;
            return end.val;
        }

        /**
         * Checks whether the circular deque is empty or not.
         */
        public boolean isEmpty() {
            return count <= 0;
        }

        /**
         * Checks whether the circular deque is full or not.
         */
        public boolean isFull() {
            return count >= size;
        }
    }


    class MyCircularDeque2 {

        private int[] deque;
        private Integer end;

        /**
         * Initialize your data structure here. Set the size of the deque to be k.
         */
        public MyCircularDeque2(int k) {
            deque = new int[k];
            end = -1;
        }

        /**
         * Adds an item at the front of Deque. Return true if the operation is successful.
         */
        public boolean insertFront(int value) {
            if (isFull()) return false;
            for (int i = end; i >= 0; i--) {
                deque[i + 1] = deque[i];
            }
            deque[0] = value;
            end++;
            return true;
        }

        /**
         * Adds an item at the rear of Deque. Return true if the operation is successful.
         */
        public boolean insertLast(int value) {
            if (isFull()) return false;
            deque[++end] = value;
            return true;
        }

        /**
         * Deletes an item from the front of Deque. Return true if the operation is successful.
         */
        public boolean deleteFront() {
            if (end == -1) return false;
            for (int i = 1; i <= end; i++) {
                deque[i - 1] = deque[i];
            }
            end--;
            return true;
        }

        /**
         * Deletes an item from the rear of Deque. Return true if the operation is successful.
         */
        public boolean deleteLast() {
            if (end == -1) return false;
            deque[end--] = 0;
            return true;
        }

        /**
         * Get the front item from the deque.
         */
        public int getFront() {
            if (end == -1) return -1;
            return deque[0];
        }

        /**
         * Get the last item from the deque.
         */
        public int getRear() {
            if (end == -1) return -1;
            return deque[end];
        }

        /**
         * Checks whether the circular deque is empty or not.
         */
        public boolean isEmpty() {
            return end == -1;
        }

        /**
         * Checks whether the circular deque is full or not.
         */
        public boolean isFull() {
            if (end == deque.length - 1) {
                return true;
            }
            return false;
        }

        public void chargeSize() {
            if (end >= deque.length - 1) {
                int[] dequeCopy = new int[deque.length * 2 + 1];//防止初始为0时多次乘2仍为0
                System.arraycopy(deque, 0, dequeCopy, 0, end);
                deque = dequeCopy;
            }
        }
    }

}
